package _dp_base;

/**
 * 2140. 解决智力问题
 */
public class No2140 {
    private int[][] questions;
    private long[] cache;

    /**
     * 1. 递归
     */
    public long mostPoints1(int[][] questions) {
        this.questions = questions;
        int n = questions.length;
        cache = new long[n];

        return dfs(0);
    }

    private long dfs(int i) {
        if (i >= questions.length) return 0;
        else if (cache[i] != 0) return cache[i];
        else return cache[i] = Math.max(dfs(i + 1 + questions[i][1]) + questions[i][0], dfs(i + 1));
    }

    /**
     * 2. 迭代
     */
    public long mostPoints2(int[][] questions) {
        int n = questions.length;
        long[] f = new long[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            int j = i + 1 + questions[i][1];
            f[i] = Math.max((j >= n ? 0 : f[j]) + questions[i][0], f[i + 1]);
        }
        return f[0];
    }
}
